
package Mapeamento.QuadTree;

import GUI.Controle;
import GUI.Obstaculos;
import java.util.ArrayList;

/*
 *    Quadtree e uma estrutura de dados formado a partir
 *  espacial dos dados. Inicialmente, os dados que representam
 *  algo bidimensionalmente sao divididos em quatro quadrantes,
 *  cujas dimensoes sao iguais e apica-se recursivamente este
 *  processo ate que alguma condiçao para o processo.
 */
public class Arvore {

    public No raiz;
    public int idUltimo;
    private int fator_de_escala = 3;
    Vertice p1, p2;
    public Obstaculos obstaculos;
    Controle controle = null;
    public ArrayList<No> lista;

    public Arvore(Controle x)
    {
        controle = x;

        // Criaçao dos Vertices do No raiz (Tamanho do Labirinto)
        p1 = new Vertice(fator_de_escala*270,0);
        p2 = new Vertice(0, fator_de_escala*220);

        // Criaçao do no Raiz (ID, tipo, Vertice 1, Vertice 2).
        // Tipos podem ser: livre, misto, ocupado.
        raiz = new No(1, Tipo.misto, p1, p2);

        idUltimo = 1;

        // Recebe a lista de obstaculos inseridos no labirinto.
        this.obstaculos = x.getObstaculos();
    }

    // Verifica se possui alguma celula mista. Se sim, a subdivide.
    public void verificar()
    {
        // Inicia a busca pela raiz
        No atual = raiz;
        No filho = raiz.filho1;
        No temp = null;

        lista = new ArrayList<No>();

        // Inicia Verificaçao
        // Realiza um loop ate identificar um No que seja misto e que possa ser dividido
        while((atual.tipo != Tipo.misto) || (atual.flag == 1) )
        {
                // Se a celula estiver livre, ou seja, sem obstaculos ela sera
                // inserida numa lista para planejamento do caminho.
                if(atual.tipo == Tipo.livre)
                {
                    // Verifia antes de inserir na lista se ja contem o objeto
                    if(!lista.contains(atual))
                    {
                        lista.add(atual);
                    }
                }


                // Verifica se o No atual nao tem filho. Modifica o No atual para o irmao
                if(filho == null)
                {
                    // Define o proximo irmao para ser o atual
                    temp = atual;
                    atual = atual.pai;
                    filho = temp;
                    atual = atual.proximoFilho(filho);
                    filho = atual.filho1;
                }else
                {
                    // Define o filho como o atual
                    atual = filho;
                    filho = atual.filho1;
                }


                // Verifica pelo id o ultimo No
                if(atual.id == -1)
                {
                    // Finaliza a busca por espaços livre
                    //System.out.println("Fim: " + lista.size());
                    atual.flag = 1;
                    break;
                }
        }

        //Verificar o tipo: dividir se ainda não foi dividido
        if(atual.flag == 0)
        {
           // Verifica tamanho da celula em relaçao ao tamanho minimo possivel
           if((atual.p1.x-atual.p2.x)>15)
           {
              // Cria os Nos filhos do No atual
              idUltimo = atual.gerarFilhos(idUltimo, atual);
              //Desenha a grade da divisao
              desenha(atual);
              //Classifica os novos filhos
              atual.classificar(obstaculos);
              // Defini a celula como já dividida
              atual.flag = 1;
              // Volta a raiz e verifica tudo novamente
              verificar();
           }else
           {
              // Tamanho inferior ao tamanho minimo possivel das celulas
              // Seta o flag para a nao divisao da celula
              atual.flag = 1;
              // Inicia a verificaçao novamente
              verificar();
           }
        }
    }

    public void desenha(No atual)
    {
        // Desenha a divisao do No atual formando os 4 novos filhos.
        controle.setaLinha(atual.filho1.p1.x, atual.filho1.p1.y, atual.filho3.p1.x, atual.filho3.p2.y,
                atual.filho1.p2.x, atual.filho1.p2.y, atual.filho4.p1.x, atual.filho4.p1.y);
    }

}
